package edu.cc321.algorithms;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author Carl
 * 
 *         2014-4-1
 */
public class Sort {

	public static <E extends Comparable<? super E>> void shellSort(List<E> a) {
		int h = 1;
		while (h < a.size() / 3)
			h = h * 3 + 1; // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ...
		for (; h >= 1; h /= 3)
			for (int i = h; i < a.size(); i++)
				for (int j = i; j >= h && a.get(j).compareTo(a.get(j - h)) < 0; j -= h)
					Collections.swap(a, j, j - h);
	}

	public static void main(String[] args) {
		List<Integer> list = new ArrayList<Integer>();
		for (int i = 10; i > 0; i--) {
			list.add(i);
		}
		shellSort(list);
		System.out.println(list);
	}
}
